//
// Created by Jinyu Zhu on 2022/4/20.
//
#include "deque"
#include "map"
#include "set"
#include "unordered_map"
#include "unordered_set"
#include "tuple"
#include "limits"

#include "algorithm_graphd.h"
#include "lib_csv/csv2.h"

#define Bool_Num(Bool_) \
  ( (Bool_) ? 1 : 0)
#define TimeStamp_Str_To_Long(Str_) \
  ( (strlen((Str_)) == 0) ? -1 : (std::stol(std::string((Str_))) ) )
#define Base_PathName(TsvPath) \
  ( (TsvPath).substr((TsvPath).find_last_of("/\\") + 1) )

void AlgorithmDirectedGraph::LoadOneTsv(const PDirectedGraph &PG, const std::string &TsvPath) {
    io::CSVReader<4, io::trim_chars<>, io::no_quote_escape<'\t'>, io::throw_on_overflow, io::no_comment >
            in(TsvPath);
    in.read_header(io::ignore_extra_column, "time", "start", "end", "relation_type");
    std::string basename = Base_PathName(TsvPath);
    char* time, *start, *end, *relation_type;
    int LineNo = 0;
    while (in.read_row(time, start, end, relation_type)) {
        LineNo++;
        bool time_nan = strlen(time) == 0;
        bool start_nan = strlen(start) == 0;
        bool end_nan = strlen(end) == 0;

        if ( (!start_nan) && (PG->NameNodeNum(start) == 0) ) { PG->AddNode(start); }
        if ( (!end_nan) && (PG->NameNodeNum(end) == 0) ) { PG->AddNode(end); }

        int start_id, end_id;
        if (!start_nan) { start_id = PG->GetNodeId(start).at(0); }
        if (!end_nan) { end_id = PG->GetNodeId(end).at(0); }

        int empty = Bool_Num(time_nan) + Bool_Num(start_nan) + Bool_Num(end_nan);

        if (empty <= 1) {
            start_id = start_nan ? end_id : start_id;
            end_id = end_nan ? start_id : end_id;
            PG->AddEdge(start_id, end_id, relation_type, TimeStamp_Str_To_Long(time), basename + "///" + std::to_string(LineNo));
        } else {
            if (start_nan && end_nan) {     // dependent node
                PG->AddNode( basename + "///" + std::to_string(LineNo), TimeStamp_Str_To_Long(time));
            } else {}  // CHECKME: node attribute, not implemented in cpp
        }
    }

}

template<class N>
bool cmp(const N& a, const N& b) {
    return std::get<1>(*a) > std::get<1>(*b);
}

PDirectedGraph AlgorithmDirectedGraph::TrackGraphN(const PDirectedGraph &PG, const std::vector<int> &StartIdV,
                                                  const int &BackStep,const int &FrontStep, const int &MaxNext,
                                                  std::set<int>& NewNodeIdSet, std::set<int>& NewEdgeIdSet) {
    int Back = BackStep;
    if (StartIdV.size() > 10) throw std::runtime_error("node id list length > 10!");

    PDirectedGraph GraphResult = DirectedGraph::New();

    // --- BackTracking ---
    std::deque<DirectedGraph::Node*> BackIter;
    std::map<int, long> TimeMap;

    if (Back > 0) {
        for (const int& StartId : StartIdV) {
            if (GraphResult->IsNode(StartId)) continue;
            if (!PG->IsNode(StartId)) throw std::runtime_error("node id " + std::to_string(StartId) + " not exists");
            DirectedGraph::Node* OldStartNode = PG->GetNodeP(StartId);
            BackIter.push_back(OldStartNode);
            GraphResult->AddNodeReplica(OldStartNode);
            TimeMap.insert({ OldStartNode->Id, std::numeric_limits<long>::max() });
        }
    } else if (Back < 0) { throw std::runtime_error("back should be >= 0"); }

    while ((!BackIter.empty()) && (Back > 0)) {
        Back -= 1;
        int BackIterSize = (int) BackIter.size();
        NewNodeIdSet.clear(); NewEdgeIdSet.clear();
        std::unordered_set<int> CurrIterNew;
        for (int i = 0; i < BackIterSize; i++) {
            DirectedGraph::Node* NodeOld = BackIter.front(); BackIter.pop_front();
            DirectedGraph::Node* NodeNew = GraphResult->GetNodeP(NodeOld->Id);

            // 剪枝, { node_id: (node, degree, [edge_id_list]) }
            std::unordered_map<int, std::tuple<DirectedGraph::Node*, int, std::vector<int> > > TargetNodeDict;
            std::unordered_map<int, std::tuple<DirectedGraph::Node*, int, std::vector<int> > > ExistedNodeDict;
            for (const int& InEdgeId: NodeOld->InEIdV) {
                DirectedGraph::Edge* InEdgeOld = PG->GetEdgeP(InEdgeId);
                // 排除自环
                if (InEdgeOld->SrcNId == InEdgeOld->DstNId) continue;
                // 排除Visited Relation
                if (NodeNew->BinSearchBinInEIdV(InEdgeId)) continue;
                long EdgeTimeStamp = (InEdgeOld->TimeStamp == -1) ? 0 : InEdgeOld->TimeStamp;
                if (EdgeTimeStamp > TimeMap.at(NodeOld->Id)) continue;

                DirectedGraph::Node* PriorNodeOld = PG->GetNodeP(InEdgeOld->GetSrcNId());
                // PriorNode是否已经存在于新图? 如果存在，则该边一定加入新图
                if (GraphResult->IsNode(PriorNodeOld->Id)) {
                    if (ExistedNodeDict.find(PriorNodeOld->Id) == ExistedNodeDict.end()) {
                        ExistedNodeDict.insert({PriorNodeOld->Id, {PriorNodeOld, PriorNodeOld->GetDeg(), {InEdgeId}}});
                    } else {
                        std::get<2>(ExistedNodeDict.at(PriorNodeOld->Id)).push_back(InEdgeId);
                    }
                } else {
                    if (TargetNodeDict.find(PriorNodeOld->Id) == TargetNodeDict.end()) {
                        TargetNodeDict.insert({PriorNodeOld->Id, {PriorNodeOld, PriorNodeOld->GetDeg(), {InEdgeId}}});
                    } else {
                        std::get<2>(TargetNodeDict.at(PriorNodeOld->Id)).push_back(InEdgeId);
                    }
                }
            }

            std::vector<std::tuple<DirectedGraph::Node*, int, std::vector<int> >* > TargetNodeList;
            for (auto &iter: TargetNodeDict) { TargetNodeList.push_back(&(iter.second)); }
            std::sort(TargetNodeList.begin(), TargetNodeList.end(), cmp<std::tuple<DirectedGraph::Node*, int, std::vector<int> >* >);
            if (TargetNodeList.size() > MaxNext) { TargetNodeList = std::vector<std::tuple<DirectedGraph::Node*, int, std::vector<int> >* >(TargetNodeList.begin(), TargetNodeList.begin() + MaxNext); }
            for (auto &iter: ExistedNodeDict) { TargetNodeList.push_back(&(iter.second)); }

            for (auto &iter: TargetNodeList) {
                DirectedGraph::Node* PriorNodeOld = std::get<0>(*iter);
                std::vector<int>& EdgeIdList = std::get<2>(*iter);

                if (CurrIterNew.find(PriorNodeOld->Id) == CurrIterNew.end()) {
                    CurrIterNew.insert(PriorNodeOld->Id); BackIter.push_back(PriorNodeOld);
                }

                for (const int& EdgeId : EdgeIdList) {
                    DirectedGraph::Edge* InEdgeOld = PG->GetEdgeP(EdgeId);
                    long EdgeTimeStamp = (InEdgeOld->TimeStamp == -1) ? 0 : InEdgeOld->TimeStamp;
                    // Add Node If not exists
                    if (!GraphResult->IsNode(PriorNodeOld->Id)) {
                        NewNodeIdSet.insert(PriorNodeOld->Id);
                        GraphResult->AddNodeReplica(PriorNodeOld);
                    }
                    DirectedGraph::Node* PriorNodeNew = GraphResult->GetNodeP(PriorNodeOld->Id);
                    // Add Edge
                    NewEdgeIdSet.insert(EdgeId);
                    GraphResult->AddEdgeReplica(InEdgeOld);
                    TimeMap[PriorNodeNew->Id] = (TimeMap.find(PriorNodeNew->Id) == TimeMap.end()) ?
                            EdgeTimeStamp : std::max(EdgeTimeStamp, TimeMap[PriorNodeNew->Id]);
                }
            }
        }
    }

    // --- FrontTracking ---
    std::deque<DirectedGraph::Node*> FrontIter;
    TimeMap = std::map<int, long>();
    int Front = FrontStep;

    if (BackStep == 0) {
        for (const int& StartId : StartIdV) {
            if (GraphResult->IsNode(StartId)) continue;
            if (!PG->IsNode(StartId)) throw std::runtime_error("node id " + std::to_string(StartId) + " not exists");
            DirectedGraph::Node* OldStartNode = PG->GetNodeP(StartId);
            FrontIter.push_back(OldStartNode);
            GraphResult->AddNodeReplica(OldStartNode);
            TimeMap.insert({ OldStartNode->Id, 0 });
        }
    } else {
        for (auto& iter : GraphResult->NodeMap) {
            int NodeId = iter.first;
            FrontIter.push_back(PG->GetNodeP(NodeId));
            for (const int& InEId: iter.second.InEIdV) {
                DirectedGraph::Edge* InE = GraphResult->GetEdgeP(InEId);
                long EdgeTimeStamp = (InE->TimeStamp == -1) ? 0 : InE->TimeStamp;
                TimeMap[NodeId] = (TimeMap.find(NodeId) == TimeMap.end()) ?
                        EdgeTimeStamp : std::min(EdgeTimeStamp, TimeMap[NodeId]);
            }
            // 无入边的点, 最小时间预初始化为0
            if (TimeMap.find(NodeId) == TimeMap.end()) { TimeMap[NodeId] = 0; }
        }
    }

    while ((!FrontIter.empty()) && (Front > 0)) {
        Front -= 1;
        int FrontIterSize = (int) FrontIter.size();

        NewNodeIdSet.clear(); NewEdgeIdSet.clear();
        std::unordered_set<int> CurrIterNew;
        for (int i = 0; i < FrontIterSize; i++) {
            DirectedGraph::Node* NodeOld = FrontIter.front(); FrontIter.pop_front();
            DirectedGraph::Node* NodeNew = GraphResult->GetNodeP(NodeOld->Id);

            // 剪枝, { node_id: (node, degree, [edge_id_list]) }
            std::unordered_map<int, std::tuple<DirectedGraph::Node*, int, std::vector<int> > > TargetNodeDict;
            std::unordered_map<int, std::tuple<DirectedGraph::Node*, int, std::vector<int> > > ExistedNodeDict;
            for (const int& OutEdgeId: NodeOld->OutEIdV) {
                DirectedGraph::Edge* OutEdgeOld = PG->GetEdgeP(OutEdgeId);
                // 排除自环
                if (OutEdgeOld->SrcNId == OutEdgeOld->DstNId) continue;
                // 排除Visited Relation
                if (NodeNew->BinSearchBinInEIdV(OutEdgeId)) continue;
                long EdgeTimeStamp = (OutEdgeOld->TimeStamp == -1) ? 0 : OutEdgeOld->TimeStamp;
                if (EdgeTimeStamp < TimeMap.at(NodeOld->Id)) continue;

                DirectedGraph::Node* NextNodeOld = PG->GetNodeP(OutEdgeOld->GetDstNId());
                // NextNode是否已经存在于新图? 如果存在，则该边一定加入新图
                if (GraphResult->IsNode(NextNodeOld->Id)) {
                    if (ExistedNodeDict.find(NextNodeOld->Id) == ExistedNodeDict.end()) {
                        ExistedNodeDict.insert({NextNodeOld->Id, {NextNodeOld, NextNodeOld->GetDeg(), {OutEdgeId}}});
                    } else {
                        std::get<2>(ExistedNodeDict.at(NextNodeOld->Id)).push_back(OutEdgeId);
                    }
                } else {
                    if (TargetNodeDict.find(NextNodeOld->Id) == TargetNodeDict.end()) {
                        TargetNodeDict.insert({NextNodeOld->Id, {NextNodeOld, NextNodeOld->GetDeg(), {OutEdgeId}}});
                    } else {
                        std::get<2>(TargetNodeDict.at(NextNodeOld->Id)).push_back(OutEdgeId);
                    }
                }
            }

            std::vector<std::tuple<DirectedGraph::Node*, int, std::vector<int> >* > TargetNodeList;
            for (auto &iter: TargetNodeDict) { TargetNodeList.push_back(&(iter.second)); }
            std::sort(TargetNodeList.begin(), TargetNodeList.end(), cmp<std::tuple<DirectedGraph::Node*, int, std::vector<int> >* >);
            if (TargetNodeList.size() > MaxNext) { TargetNodeList = std::vector<std::tuple<DirectedGraph::Node*, int, std::vector<int> >* >(TargetNodeList.begin(), TargetNodeList.begin() + MaxNext); }
            for (auto &iter: ExistedNodeDict) { TargetNodeList.push_back(&(iter.second)); }


            for (auto &iter: TargetNodeList) {
                DirectedGraph::Node* NextNodeOld = std::get<0>(*iter);
                std::vector<int>& EdgeIdList = std::get<2>(*iter);

                if (CurrIterNew.find(NextNodeOld->Id) == CurrIterNew.end()) {
                    CurrIterNew.insert(NextNodeOld->Id); FrontIter.push_back(NextNodeOld);
                }

                for (const int& EdgeId : EdgeIdList) {
                    DirectedGraph::Edge* OutEdgeOld = PG->GetEdgeP(EdgeId);
                    long EdgeTimeStamp = (OutEdgeOld->TimeStamp == -1) ? 0 : OutEdgeOld->TimeStamp;
                    // Add Node If not exists
                    if (!GraphResult->IsNode(NextNodeOld->Id)) {
                        NewNodeIdSet.insert(NextNodeOld->Id);
                        GraphResult->AddNodeReplica(NextNodeOld);
                    }
                    DirectedGraph::Node* NextNodeNew = GraphResult->GetNodeP(NextNodeOld->Id);
                    // Add Edge
                    NewEdgeIdSet.insert(EdgeId);
                    GraphResult->AddEdgeReplica(OutEdgeOld);
                    TimeMap[NextNodeNew->Id] = (TimeMap.find(NextNodeNew->Id) == TimeMap.end()) ?
                                               EdgeTimeStamp : std::min(EdgeTimeStamp, TimeMap[NextNodeNew->Id]);
                }
            }
        }

    }



    return GraphResult;
}
